0021. 分治 vs 动态规划
1. 🎯 本节内容
- 分治算法和动态规划算法对比
2. 🫧 评价
分治算法和动态规划算法都属于算法设计中的重要范式，经常被放在一起比较。
简单来说：动态规划是分治算法的“加强版”，专门为解决具有重叠子问题和最优子结构的问题而设计，通过存储子问题的解来避免重复计算，从而提高效率。两者不是完全无关，而是存在明显的演进和优化关系。
- 朴素分治 -> 遇到重叠子问题时效率低下（如朴素递归计算斐波那契数）
- 带备忘录的分治 -> 添加缓存存储已计算子问题的解
- 动态规划 -> 系统性地将带备忘录的分治转化为迭代形式
3. 🤔 相似之处都有哪些？
- 问题分解思想：两者都基于“分而治之”的思想，将复杂问题分解为更小的子问题
- 递归结构：通常都使用递归或自底向上的方式求解
- 子问题求解：都需要解决子问题，然后组合子问题的解得到原问题的解
4. 🤔 主要区别都有哪些？
| 特征 | 分治算法 | 动态规划 |
|---|---|---|
| 子问题重叠性 | 子问题通常不重叠（如归并排序、快速排序） | 子问题高度重叠（如斐波那契数列） |
| 最优子结构 | 不一定要求最优子结构 | 必须具有最优子结构 |
| 存储子问题解 | 不存储子问题的解（重复计算） | 存储子问题的解（避免重复计算） |
| 适用场景 | 问题可划分为独立子问题 | 问题具有重叠子问题和最优子结构 |
| 典型例子 | 归并排序、快速排序、二分查找 | 背包问题、最短路径、编辑距离 |
5. 🤔 两者之间的关系是？
- 继承与发展：动态规划继承了分治的分解思想，但针对重叠子问题进行了优化
- 技术演进：当发现分治算法存在大量重复计算时，可以考虑改用动态规划
- 设计思维：分治是"先分后合"，动态规划是"先小后大"（自底向上或带备忘录）
- 互补而非对立：有些问题既可用分治也可用动态规划，只是效率不同
6. 🤔 动态规划一定比分治好吗？
不一定。
虽然说动态规划是分治的“加强版”，但在实际应用中，适用分治的场景不一定适用动态规划，反之亦然。
分治适合"分而独立"的问题，动态规划适合"分而重叠"的最优化问题。不是谁更好，而是谁更合适。
实际开发时，还是要根据具体问题的特点来选择：
适合用分治的场景：
- 子问题独立：如归并排序、快速排序，子问题之间没有重叠，用分治更简洁
- 不需要存储：问题规模大，存储所有子问题的解会消耗大量内存
- 并行计算：分治的子问题独立，容易并行处理（如 MapReduce）
适合用动态规划的场景：
- 子问题重叠：如斐波那契、背包问题，大量重复计算
- 最优子结构：问题要求最优解，且最优解可由子问题最优解构成
- 空间可接受：存储子问题解的空间开销在可接受范围内